package 数据结构专栏.简单级别;

import 数据结构专栏.B_链表专栏.ListNode;

/**
 * @DESC _递归专项练习
 * 递归其实就是栈
 * @Author tzq
 * @Date 2020-03-30 16:00
 *
 * @参考
 * https://lyl0724.github.io/2020/01/25/1/
 *
 * 解递归题的三部曲：
 *
 * 找整个递归的终止条件：递归应该在什么时候结束？
 * 找返回值：应该给上一级返回什么信息？
 * 本级递归应该做什么：在这一级递归中，应该完成什么任务？
 *
 **/
public class _递归专项练习 {
    public static void main(String[] args) {
        System.out.println(sum(10));
    }

    /**
     * 前n项和
     * <p>
     * 使用递归必需明确
     * 1.递归的结束条件  获取到1的时候结束
     * 2.递归的目标  获取下一个被加的数字(n-1
     *
     * @param n
     * @return
     */
    public static int sum(int n) {
        if (n == 1) return 1;
        return n + sum(n - 1);

    }


    /**
     * 反转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverse(ListNode head) {
        if (head == null || head.next == null) return head;
        ListNode next = head.next;
        head.next = null;
        ListNode reverse = reverse(next);
        next.next = head;
        return reverse;
    }

    /**
     * 迭代方式反转链表
     *
     * @param head
     * @return
     */
    public static ListNode reverseByIterator(ListNode head) {
        ListNode pre = null, curr = null;
        while (head.next != null) {
            ListNode tempNext = head.next;
            head.next = pre;
            pre = curr;
            curr = tempNext;
        }
        return pre;
    }


}
